//
// Created by 98770 on 2022/12/28.
//

#include "avl_tree.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int times;//记录比较次数
//抛出错误信息并终止程序
static void ThrowError(char *s) {
    printf("%s\n", s);
    exit(0);
}

int Max(int a, int b) {
    if (a >= b)
        return a;
    else
        return b;
}

struct AvlNode {
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

static int Height(Position P) {
    if (P == NULL)
        return -1;
    else
        return P->Height;
}

AvlTree MakeEmpty(AvlTree T) {
    if (T) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X, AvlTree T) {
    Position P;
    P = T;
    times=0;
    while (P != NULL) {
        times++;
        if (P->Element < X)
            P = P->Right;
        else if (P->Element > X)
            P = P->Left;
        else
            break;
    }
    times--;
    return P;
}

Position FindMin(AvlTree T) {
    if (T == NULL)
        return NULL;
    while (T->Left != NULL)
        T = T->Left;
    return T;
}

Position FindMax(AvlTree T) {
    if (T == NULL)
        return NULL;
    while (T->Right != NULL)
        T = T->Right;
    return T;
}

static Position SingleRotateWithLeft(Position K2);

static Position SingleRotateWithRight(Position K2);

static Position DoubleRotateWithLeft(Position K3);

static Position DoubleRotateWithRight(Position K3);

AvlTree Insert(ElementType X, AvlTree T) {
    if (T == NULL) {//创建一个节点的树
        T = malloc(sizeof(struct AvlNode));
        if (T == NULL)
            ThrowError("Unable to Malloc an AvlNode");
        else {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2) {
            if (X < T->Left->Element)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
        }
    }
    else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2) {
            if (X > T->Right->Element)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
        }
    }
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}
//递归删除
AvlTree Delete(ElementType X, AvlTree T) {
    if(T==NULL)
        return T;
    if(T->Element<X)
        T->Right= Delete(X,T->Right);
    else if(T->Element>X)
        T->Left= Delete(X,T->Left);
    else{//找到待删除的节点
        if(T->Left&&T->Right){//有两个孩子
            Position p=T->Right;
            p=FindMin(p);
            T->Element=p->Element;
            T->Right= Delete(p->Element,T->Left);
        }else{
            Position p= T->Left?T->Left:T->Right;
            free(T);
            return p;
        }
    }
    if(Height(T->Left)- Height(T->Right)>=2){//删除邮编引起失衡
        if(Height(T->Left->Left)> Height(T->Left->Right))
            T= SingleRotateWithRight(T);
        else
            T= DoubleRotateWithRight(T);
    }else if(Height(T->Right)- Height(T->Left)>=2) {//删除左边引起失衡
        if (Height(T->Right->Left) > Height(T->Right->Right))
            T = DoubleRotateWithLeft(T);
        else
            T = SingleRotateWithLeft(T);
    }
    T->Height= Max(Height(T->Left), Height(T->Right))+1;
    return T;
}
//单旋转
static Position SingleRotateWithLeft(Position K2) {
    Position K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;
    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
    return K1;
}

static Position SingleRotateWithRight(Position K2) {
    Position K1;
    K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;
    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
    return K1;
}
//双旋转
static Position DoubleRotateWithLeft(Position K3) {
    K3->Left = SingleRotateWithRight(K3->Left);
    return SingleRotateWithLeft(K3);
}

static Position DoubleRotateWithRight(Position K3) {
    K3->Right = SingleRotateWithLeft(K3->Right);
    return SingleRotateWithRight(K3);
}

